package _前缀和;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/8/9 16:54
 * <p>
 * 功能描述:
 */
public class _0560 {

    /**
     * https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/
     *
     * Q: 为什么哈希表需要先put(0,1)？
     * A: 1.因为数组中有些数直接就等于k
     *    2.这是因为要保持哈希表的定义，key 是当前位置之前的所有元素的和（依然是前缀和），value 是对应的个数。
     *    在遍历开始之前，当前位置之前的所有元素为空，可以认为和是 0，对应的个数就为 1。
     *
     */
    public int subarraySum(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

}
